package sort;

import java.util.Arrays;
import java.util.function.IntUnaryOperator;

/**
 * @Author: Dang Qi
 * @Date: 2021/4/7  16:48
 * @Description:
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] a= {5,2,6,4,7,8};
        sort(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));
    }
    public static void quickSort(int[] a, int i, int j){
        if(i>=j) return;
        int k = partion(a, i, j);
        quickSort(a, i, k-1);
        quickSort(a, k+1, j);
    }
    public static int partion(int[] a, int lo, int hi){
        int v = a[0];
        int index = lo+1;
        for(int i = index; i <= hi; i++){
            if(a[i] <= v) swap(a, i, index++);
        }
        swap(a, index-1, lo);
        return index-1;
    }

    public static void swap(int[] a, int i, int j){
        if(i==j || a[i] == a[j]) return;
        a[i] = a[i] ^ a[j];
        a[j] = a[i] ^ a[j];
        a[i] = a[j] ^ a[i];
    }
    public static void sort(int []a, int lo, int hi)
    {
        if(hi<=lo) return ;
        int it = lo;
        int i = lo+1;
        int gt = hi;
        int v = a[lo];
        while(i<=gt) {
            if(a[i] < v) swap(a, i++, it++);
            else if(a[i]>=v) swap(a, i, gt--);
            else i++;
        }
        sort(a, lo, it-1);
        sort(a, gt+1, hi);
    }

}
